#include <iostream>
using std::cout;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() {}
    ListNode(int val, ListNode *next) : val(val), next(next) {}
};

class Solution
{
public:
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        if (head == nullptr || n == 0)
            return head;
        ListNode* dummyHead = new ListNode();
        dummyHead->next = head;
        ListNode *fast = dummyHead;
        ListNode *slow = head;
        n++;
        while (n--)
        {
            fast = fast->next;
        }

        while (1)
        {
            fast = fast->next;
            slow = slow->next;
            if (fast == nullptr)
                break;
        }
        ListNode *tmp = slow->next;
        slow->next = tmp->next;
        delete tmp;
        return head;
    }
};

int main(int argc, char const *argv[])
{
    ListNode *head = new ListNode();
    head->val = 1;
    head->next = nullptr;
    ListNode *cur = head;
    for (int i = 1; i < 5; ++i)
    {
        ListNode *newNode = new ListNode();
        newNode->next = nullptr;
        newNode->val = i + 1;
        cur->next = newNode;
        cur = newNode;
    }
    cur = head;
#if 1
    while (cur)
    {
        if (cur->next != nullptr)
            cout << cur->val << "->";
        else
            cout << cur->val << "\n";

        cur = cur->next;
    }
#endif
    Solution s;
    head = s.removeNthFromEnd(head, 3);
    cur = head;
    // cur = s.swapPairs(head);
    while (cur)
    {
        if (cur->next != nullptr)
            cout << cur->val << "->";
        else
            cout << cur->val << "\n";

        cur = cur->next;
    }
    getchar();
    return 0;
}
